package arraylist;

//只保存String类型的数据，正常的调用方法保存的是泛型类型的数据

public class MyArrayList {
    //通过这个数组，来表示顺序表中的元素
    private String[] data = null;
    //表示有效元素的个数
    private int size = 0;

    public MyArrayList() {
        //默认初始容量为10
        data = new String[10];
    }

    public MyArrayList(int capacity) {
        if (capacity <= 10) {
            capacity = 10;
        }
        data = new String[capacity];
    }

    //实现扩容操作
    private void resize() {
        //1.创建更长的数组，新的数组容量是原来的1.5倍
        String[] newData = new String[data.length + (data.length >> 1)];
        //2.把旧数组的元素，复制到新数组上
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        //3.更新新数组代替旧数组
        data = newData;
    }

    //实现尾插操作
    //时间复杂度为o（1）
    public void add(String elem) {
        //把elem放到data的最后一个位置上，也就是下标为size的位置
        //[0,size)区间是有效元素
        //需要实现扩容逻辑
        if (size >= data.length) {
            resize();
        }
        data[size] = elem;
        size++;
    }

    //往中间位置插入，往index元素之前插入，确保新元素的下标就是index
    //时间复杂度为O（N）
    public void add(int index, String elem) {
        //1.判定index是否合法
        //所以此处要明确是否写作index <= 0或者index >= size??
        //边界值都需要重点讨论
        //如果index为0，意思是插入完毕后，元素就处于0号位置，就相当于头插
        //如果index为size，意思是插入完毕后，元素就处于size位置，就相当于尾插
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        if (size >= data.length) {
            //进行扩容操作
            resize();
        }

        //把元素放到index位置上，进行搬运，把index之后的元素，都往后移动一个位置
        //需要从前往后遍历
        //带入size为6的时候，最后一个元素下标就是5
        //初始的搬运就是data[5] 放到data[6]位置上
        //最终的代码就是data[i+1] = data[i]
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        //把新元素放到index位置上
        data[index] = elem;
        size++;
    }

    //按照下标删除
    //返回被删除元素的值
    public String remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        //提前把删除元素的值保存一份，否则后面删除的时候就会覆盖
        String elem = data[index];
        //也是需要进行搬运的
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size--;
        return elem;
    }

    //按照元素值来删除
    //如果删除成功，返回true，否则返回false
    //如果elem本身不存在，则认为是删除失败
    public boolean remove(String elem) {
        //先找到elem对应的位置在哪里
        int removePos = 0;
        for (; removePos < size; removePos++) {
            if (data[removePos].equals(elem)) {
                //找到了要删除元素的下标
                break;
            }
        }
        //上述循环结束后，有两种可能
        //1.找到了elem
        //2.没找到elem，i和size相等了，说明elem不存在
        if (removePos == size) {
            //没找到
            return false;
        }
        //拿着removePos进行删除
        //拿着搬运操作
        for (int i = removePos; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size--;
        remove(removePos);
        return true;
    }

    //获取指定位置的元素
    public String get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        return data[index];
    }

    //修改指定位置的元素
    public void set(int index, String elem) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
        data[index] = elem;
    }

    //删除所有元素
    public void clear() {
        //不需要把数组中的每个元素都设为null之类的
        size = 0;
    }

    //查看是否包含某元素
    public boolean contains(String elem) {
        //遍历整个数组，看elem元素是否存在，存在就返回true
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem)) {
                return true;
            }
        }
        //return false;
        return indexOf(elem) != -1;
    }

    //查看是否存在某个元素，有的话返回下标，没有的话返回-1
    public int indexOf(String elem) {
        //遍历，看elem元素是否存在，存在就返回他的下标
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    //从后往前遍历寻找某个元素
    public int lastIndexOf(String elem) {
        //从后往前遍历
        for (int i = size - 1; i >= 0; i--) {
            if (data[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }

    //添加一些元素
    //[fromIndex, toIndex)
    public MyArrayList subList(int fromIndex, int toIndex) {
        //创建一个新的MyArrayList对象，把上述区间的元素添加到新的对象中
        //注意边界值，formIndex为0是合法的，toIndex如果是size也是合法的
        //formIndex==toIndex也是合法的，得到了空的区间
        if (fromIndex < 0 || toIndex > size || fromIndex > toIndex) {
            throw new IndexOutOfBoundsException("fromIndex:" + fromIndex + ", toIndex:" + toIndex + ", Size:" + size);
        }
        MyArrayList subList = new MyArrayList(toIndex - fromIndex);
        for (int i = fromIndex; i < toIndex; i++) {
            String elem = this.get(i);
            subList.add(elem);
        }
        return subList;
    }

    @Override
    public String toString() {
        //把有效元素转为字符串，并拼接到一起
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(data[i]);
            if (i < size - 1) {
                //如果i是size-1，说明是最后一个元素，不需要加，
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //测试尾插
    //将每个功能点的测试代码单独领出来作为一个测试方法
    //这种测试思路称为单元测试
    private static void test1() {
        MyArrayList list = new MyArrayList();
        list.add("hellw");
        list.add("world");


        System.out.println(list);
    }

    //测试中间位置插入
    private static void test2() {
        MyArrayList list = new MyArrayList();
        list.add(0, "aaa");
        list.add(0, "bbb");
        list.add(2, "ccc");
    }

    //测试删除操作
    private static void test3() {
        MyArrayList list = new MyArrayList();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");
        String elem = list.remove(1);
        System.out.println(elem);
        System.out.println(list);
    }

    private static void test4() {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");

        boolean ret = list.remove("xx");
        System.out.println(ret);
        System.out.println(list);
    }

    //测试是否包含元素
    private static void test5() {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");

        System.out.println(list.contains("xx"));
    }

    private static void test6() {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        System.out.println(list.indexOf("x"));
    }

    private static void test7() {
        MyArrayList list = new MyArrayList();
        list.add("aa");
        list.add("bb");
        list.add("cc");
        list.add("dd");
        System.out.println(list.subList(1, 3));
    }

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
    }
}